BZOJ 1520 Szk-Schools

Description


Input

Output

如果有可行解, 输出最小代价,否则输出NIE.

Sample Input

5
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1

Sample Output

9

Solution

网络流水题
(水题WA了好几发,感觉最近自己蠢得不行)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>

#define maxn 400+5
#define maxm 80800+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v,w,c;
int next;
}s[maxm];

queue<int> q;
int dis[maxn],inq[maxn],par[maxn];
int first[maxn],ind;
int m[maxn],a[maxn],b[maxn],k[maxn];
int n,S,T,ans,cost;

void insert(int u,int v,int w,int c)
{

s[ind]=(sides){u,v,w,c,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,-w,0,first[v]},first[v]=ind++;
}

void costflow()
{

while( true ){
for(int i=S;i<=T;i++) dis[i]=INT_MAX;
dis[S]=0,q.push(S);
while( !q.empty() ){
int sd=q.front();q.pop();
inq[sd]=0;
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i].c>0 && dis[s[i].v]>dis[sd]+s[i].w ){
dis[s[i].v]=dis[sd]+s[i].w;
par[s[i].v]=i;
if( !inq[s[i].v] ){
inq[s[i].v]=1;
q.push(s[i].v);
}
}
}
if( dis[T]==INT_MAX ) break;
int cur,flow=INT_MAX;
cur=T;
while( cur!=S ){
flow=min(flow,s[par[cur]].c);
cur=s[par[cur]].u;
}
cur=T;
while( cur!=S ){
s[par[cur]].c-=flow,s[par[cur]^1].c+=flow;
cost+=s[par[cur]].w*flow;
cur=s[par[cur]].u;
}
ans+=flow;
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1520.in","r",stdin);
freopen("1520.out","w",stdout);
#endif
scanf("%d",&n);
set(first,-1);
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&m[i],&a[i],&b[i],&k[i]);
S=0,T=2*n+1;
for(int i=1;i<=n;i++)
insert(S,i,0,1),insert(n+i,T,0,1);
for(int i=1;i<=n;i++)
for(int j=a[i];j<=b[i];j++)
insert(i,n+j,abs(m[i]-j)*k[i],1);
costflow();
if( ans==n ) printf("%d",cost);
else printf("NIE");
return 0;
}